# 自研的表格识别评价指标 算法层
def damerau_levenshtein_distance(string1, string2):
    m = len(string1)
    n = len(string2)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    # 初始化第 1 列  一个空字符到其他字符的操作数
    for i in range(m + 1):
        d[i][0] = i
    # 初始化第 1 行  一个空字符到其他字符的操作数
    for j in range(n + 1):
        d[0][j] = j
    # 自底向上递推计算每个 d[i][j] 的值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if string1[i - 1] == string2[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1
            # if i > 1 and j > 1 and string1[i - 1] == string2[j - 2] and string1[i - 2] == string2[j - 1]:
            #     d[i][j] = min(d[i][j], d[i - 2][j - 2] + 1)
    return d[m][n]

chars_scale = 0
def tree_distance(tree1, tree2):
    m = len(tree1)
    n = len(tree2)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    # 初始化第 1 列  其他字符到空字符的操作数
    d[0][0] = 0
    for i in range(1, m + 1):
        lines_dist = 0
        for k in range(len(tree1[i - 1][1])):
            lines_dist = lines_dist + len(tree1[i - 1][1][k])
        d[i][0] = d[i - 1][0] + tree1[i - 1][0][1] - tree1[i - 1][0][0] + 1 + tree1[i - 1][0][3] - tree1[i - 1][0][
            2] + 1 + lines_dist * chars_scale
    # 初始化第 1 行  一个空字符到其他字符的操作数
    for j in range(1, n + 1):
        lines_dist = 0
        for k in range(len(tree2[j - 1][1])):
            lines_dist = lines_dist + len(tree2[j - 1][1][k])
        d[0][j] = d[0][j - 1] + tree2[j - 1][0][1] - tree2[j - 1][0][0] + 1 + tree2[j - 1][0][3] - tree2[j - 1][0][
            2] + 1 + lines_dist * chars_scale
    # 自底向上递推计算每个 d[i][j] 的值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if tree1[i - 1][0] == tree2[j - 1][0] and tree1[i - 1][1] == tree2[j - 1][1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                # str1 = tree1[i - 1][1]
                # str2 = tree2[j - 1][1]
                # bbb = int(tree1[i-1][0] != tree2[j-1][0]) + int(tree1[i-1][1] != tree2[j-1][1])
                #
                # temp1 = d[i - 1][j]
                # temp2 = d[i][j - 1]
                # temp3 = d[i - 1][j - 1]
                # 一个cell 有多行
                lines_dist = 0
                for k in range(len(tree1[i - 1][1])):
                    lines_dist = lines_dist + len(tree1[i - 1][1][k])
                # 如果正上方，则需要执行删除操作
                d1 = d[i - 1][j] + tree1[i - 1][0][1] - tree1[i - 1][0][0] + 1 + tree1[i - 1][0][3] - tree1[i - 1][0][
                    2] + 1 + lines_dist * chars_scale

                # 如果来自左方，需要执行插入操作
                lines_dist = 0
                for k in range(len(tree2[j - 1][1])):
                    lines_dist = lines_dist + len(tree2[j - 1][1][k])
                d2 = d[i][j - 1] + tree2[j - 1][0][1] - tree2[j - 1][0][0] + 1 + tree2[j - 1][0][3] - tree2[j - 1][0][
                    2] + 1 + lines_dist * chars_scale

                # 一个cell 有多个行 计算每个行的编辑距离，作为一个cell 中文字的编辑距离
                lines_dist = 0
                for k in range(max(len(tree1[i - 1][1]), len(tree2[j - 1][1]))):
                    if len(tree1[i - 1][1]) < k + 1:
                        tree1[i - 1][1].append("")
                    if len(tree2[j - 1][1]) < k + 1:
                        tree2[j - 1][1].append("")
                    lines_dist = lines_dist + damerau_levenshtein_distance(tree1[i - 1][1][k], tree2[j - 1][1][k])

                # 如果来自斜上方则要进行替换  在长度和宽度移动多少，后面的两个min 是在长度固定的情况下位置移动多少
                d3 = d[i - 1][j - 1] + lines_dist * chars_scale + abs((tree2[j - 1][0][1] - tree2[j - 1][0][0] + tree2[j - 1][0][3] -
                                                         tree2[j - 1][0][2]) - (tree1[i - 1][0][1] - tree1[i - 1][0][0]
                                                                                + tree1[i - 1][0][3] - tree1[i - 1][0][
                                                                                    2])) + \
                     min(abs(tree2[j - 1][0][0] - tree1[i - 1][0][0]), abs(tree2[j - 1][0][1] - tree1[i - 1][0][1])) + \
                     min(abs(tree2[j - 1][0][2] - tree1[i - 1][0][2]), abs(tree2[j - 1][0][3] - tree1[i - 1][0][3]))

                d[i][j] = min(d1, d2, d3)
            # if i > 1 and j > 1 and string1[i - 1] == string2[j - 2] and string1[i - 2] == string2[j - 1]:
            #     d[i][j] = min(d[i][j], d[i - 2][j - 2] + 1)
    return d[m][n]/max(d[0][n], d[m][0])

def tree_distance_simple(tree1, tree2):
    m = len(tree1)
    n = len(tree2)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    # 初始化第 1 列  其他字符到空字符的操作数
    d[0][0] = 0
    for i in range(1, m + 1):
        # 行跨度
        row_span = tree1[i - 1][0][1] - tree1[i - 1][0][0] + 1
        # 列跨度
        col_span = tree1[i - 1][0][3] - tree1[i - 1][0][2] + 1
        d[i][0] = d[i - 1][0] + row_span + col_span
    # 初始化第 1 行  一个空字符到其他字符的操作数
    for j in range(1, n + 1):
        row_span = tree2[j - 1][0][1] - tree2[j - 1][0][0] + 1
        col_span = tree2[j - 1][0][3] - tree2[j - 1][0][2] + 1
        d[0][j] = d[0][j - 1] + row_span + col_span
    # 自底向上递推计算每个 d[i][j] 的值
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if tree1[i - 1][0] == tree2[j - 1][0] and tree1[i - 1][1] == tree2[j - 1][1]:
                d[i][j] = d[i - 1][j - 1]
            else:

                # 如果正上方，则需要执行删除操作
                d1 = d[i - 1][j] + tree1[i - 1][0][1] - tree1[i - 1][0][0] + 1 + tree1[i - 1][0][3] - tree1[i - 1][0][
                    2] + 1

                # 如果来自左方，需要执行插入操作
                d2 = d[i][j - 1] + tree2[j - 1][0][1] - tree2[j - 1][0][0] + 1 + tree2[j - 1][0][3] - tree2[j - 1][0][
                    2] + 1

                # 如果来自斜上方则要进行替换
                # 替换一个cell的操作数包括两部分，一部分是cell大小操作数，另一部分是位置操作数。
                # cell大小的操作数是二者跨行列之和的差值
                # cell的位置操作数是
                # 二者行位置操作数和列位置操作数之和。
                # 行位置操作数，先计算行起点差值与终点差值，两个差值的的最小值。
                # 列位置操作数同理。
                d3 = d[i - 1][j - 1] + abs((tree2[j - 1][0][1] - tree2[j - 1][0][0] + tree2[j - 1][0][3] -
                                                         tree2[j - 1][0][2]) - (tree1[i - 1][0][1] - tree1[i - 1][0][0]
                                                                                + tree1[i - 1][0][3] - tree1[i - 1][0][
                                                                                    2])) + \
                     min(abs(tree2[j - 1][0][0] - tree1[i - 1][0][0]), abs(tree2[j - 1][0][1] - tree1[i - 1][0][1])) + \
                     min(abs(tree2[j - 1][0][2] - tree1[i - 1][0][2]), abs(tree2[j - 1][0][3] - tree1[i - 1][0][3]))

                d[i][j] = min(d1, d2, d3)
            # if i > 1 and j > 1 and string1[i - 1] == string2[j - 2] and string1[i - 2] == string2[j - 1]:
            #     d[i][j] = min(d[i][j], d[i - 2][j - 2] + 1)
    return d[m][n]/max(d[0][n], d[m][0])


if __name__ == '__main__':
    a = [1, 2, "adf "]
    b = [2, 3, "a125 "]
    tree1 = []
    tree2 = []
    for i in range(0, 3):
        tree1.append(a)
    for i in range(0, 2):
        tree2.append(b)
    tree_distance(tree1, tree2)

    pass
